'''
https://leetcode.cn/problems/find-the-index-of-the-large-integer
'''

# """
# This is ArrayReader's API interface.
# You should not implement it, or speculate about its implementation
# """
# class ArrayReader(object):
#	 # Compares the sum of arr[l..r] with the sum of arr[x..y]
#	 # return 1 if sum(arr[l..r]) > sum(arr[x..y])
#	 # return 0 if sum(arr[l..r]) == sum(arr[x..y])
#	 # return -1 if sum(arr[l..r]) < sum(arr[x..y])
#    def compareSub(self, l: int, r: int, x: int, y: int) -> int:
#
#	 # Returns the length of the array
#    def length(self) -> int:
#


class Solution:
    def getIndex(self, reader: 'ArrayReader') -> int:
        n = reader.length()
        l, r = 0, n - 1
        if n & 1:
            mid = l + r >> 1
            res = reader.compareSub(l, mid-1, mid+1, r)
            if res == 0:
                return mid
            elif res < 0:
                l, r = mid+1, r
            else:
                l, r = l, mid-1

        while l <= r:
            print(l, r, n)
            if l == r:
                return l
            mid = l + r >> 1
            if (r - l + 1) & 1:
                # 奇数区间
                res = reader.compareSub(l, mid-1, mid+1, r)
                if res == 0:
                    return mid
                elif res < 0:
                    l = mid+1
                else:
                    r = mid-1
            else:
                # 偶数区间
                res = reader.compareSub(l, mid, mid + 1, r)
                if res == 0:
                    return mid
                elif res < 0:
                    l = mid + 1
                else:
                    r = mid
        return -1


